決定要拆章節了，
這篇只有 5.1，
5.2 5.3 放明天，因為我好累。

這章會提到 replication，
也就是把資料複製到多個節點（稱為 replica）上，
這使得分散式系統能夠容錯，
當一個節點出事了，
還有其他節點能幫忙。
另外，也能做 load balancing，
例如很多人要讀某筆資料，可以不用都向同個伺服器要，
而可以分流到這些 replica 上。

5.1 Replication

資料如果不會更動，做 replication 很簡單，
就只是複製過去，happy ending。
所以 replication 主要的困難點在於資料會異動。

更新遠端資訊可能發生的問題

通常使用者端會與系統做一些互動，
而對系統的資料有所異動。

例如考慮按讚這件事：
![[Screen Shot 2021-09-21 at 4.45.49 PM.png]]
當使用者對貼文點讚，
遠端資料庫收到了，但回覆的 ack 封包遺失，
使用者端因此認為對方沒收到，重傳封包。

而遠端伺服器，每收到一個點讚封包，
就把 counter++，
才不管到底是不是同一個使用者重傳的封包，
這樣會導致重複計算很多次讚。

如何避免這樣的情況呢？
除了想辦法辨識重複的封包（deduplicate），
還可以把程式邏輯設計為 idempotence。

Idempotence

如果 f(x) = f(f(x))，我們說這個 function 是 idempotence。

也就是無論按幾次讚，效果都跟按一次一樣。
這樣就不需要額外做 deduplicate。

以同樣的例子來說，
原來設計 counter +=1 並不是 idempotence。
但如果改成當封包一來，把 userid 加入 likeset，
按讚數再透過這個 set 計算數量，就是 idempotence。

choices of retry behavior

對於重傳的行為，有下列三種含義（semantics），
可以幫助我們釐清需求、思考怎麼設計程式。

• at-most-one
  就傳一次，有可能因為封包遺失而沒更新到。
• at-least-one
  一直重傳直到收到 ack 包。可能重複更新。
• exactly-one
  重傳 + idempotence or dedup

adding then removing again 1

一個程式是 idempotence，還會有其他問題嗎？

如果今天某個數值能夠被不同的使用者更動，
可能會有下面這個狀況：
![[Screen Shot 2021-09-21 at 5.07.44 PM.png]]
2 個 client 對 1 個 server，
按讚和取消讚可以被不同使用者操作，
client 1 想要按讚，
client 2 想取消按讚，
以結果來說，最後應該要是取消讚的情況。
然而 client 1 卻因為 ack 封包遺失而重傳，
那麼即使這個程式被設計為 idempotence，也會因此再把讚加回來。

adding and removing again 2

如果考慮 1 個 client 對 2 個 replicas 同時做更新，
![[Screen Shot 2021-09-21 at 5.23.16 PM.png]]
情況一，client 先增加 x，而後希望移除 x。卻因為其中一個移除 x 的封包遺失導致 A、B 伺服器不一致。
情況二，client 只想增加 x。而因為其中一個增加 x 的封包遺失，導致 A、B 伺服器不一致。

這兩個情況最後的結果是相同的，
都會造成 A 上面有 x，B 沒有。
然而這並不是 client 想要的結果。

今天 replica 之間的狀態不一致時，
肯定是哪裡出了問題，
但如果沒辦法分辨到底是哪種情況，
那就不可能恢復。

Timestamp 與 tombstone

為了解決上述問題，要做兩件事：

1. 每個動作都附上 logical timestamp
2. 刪除資料時不真的刪掉東西，而是寫入一個特別的資料（tombstone）

當兩個 replicas 發現衝突，
要讓狀態變回正確且一致時 （anti-entropy），
有 tombstone，才能夠分辨這筆資料到底是還沒產生、還是被刪除了？
有 timestamp，才能夠分辨到底那個紀錄是最新的。
使得 anti-entropy 過程順利。

前面提到 2 個 client 對 1 個 server 同時做更新的問題，
也剛好得以解決：
因為重傳的訊息擁有與原訊息相同的 timestamp，
所以當後來的更新到達並影響了伺服器狀態後，
重傳的訊息的 timestamp 較小，而被捨棄。

當多個 client 對同一筆資料做更新

當多個 client 對同一筆資料做更新，
到底要聽誰的呢？

1. Last writer wins (LWW)

• 使用 total order 的 timestamp，eg. lamport clock
  有了 total order，
  若 t1 > t2，就留下 t1 的訊息，捨棄 t2 的。
• data lose
  如果有多個 concurrent 的更新，
  只有最大 timestamp 的更新會影響這個系統。

2. Multi-value register

• 使用 partial order 的 timestamp，eg. vector clock
  可以知道哪些是確實要被覆蓋掉的舊數值，
  而哪些更新是 concurrent 的。
  這些 concurrent 的事件稱為 conflicts 或 siblings，
  透過後續的處理（第 8 章）去做合併。